Number of Islands
Leetcode #200 | Medium | Графы | Матрица | DFS
Идея
DFS по матрице, если встретили 1, то запускаем dfs, в рекурсии обходим всех соседей и посещенные 1 закрашиваем в # чтобы не было повторов
Big-O
- Время
O(MN) - Память
O(MN)
Код
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') { res++; dfs(grid, r, c); }
}
}
return res;
}
private void dfs(char[][] g, int r, int c) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] == '0') return;
g[r][c] = '0';
dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);
}
}